package 堆;

import java.util.*;

public class Leedcode347前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {

        //用来保存数组中出现的频率
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        //遍历数组保存到map中
        for (int i = 0; i < nums.length; i++) {
              if (map.containsKey(nums[i])){
                  int temp = map.get(nums[i]);
                  map.put(nums[i],temp+1);
              }else {
                  map.put(nums[i],1);
              }
        }
        List<Num> lists = new ArrayList<>();
        //遍历map集合，将map集合的key，val保存到对象中，对对象进行排序
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){

            lists.add(new Num(entry.getKey(),entry.getValue()));

        }
        //将lists中的所有数排序
        lists.sort(new NumComp());


        int i = 0;
        int[] arr = new int[k];
        while (i < k){
            arr[i] = lists.get(i).key;
            i++;
        }
        return arr;
    }
}
class Num{
    int key;
    int val;

    public Num(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
class NumComp implements Comparator<Num> {

    @Override
    public int compare(Num o1, Num o2) {
        return  o2.val - o1.val;
    }
}


